﻿#include <iostream>

using namespace std;

static void swap(int* pArr, size_t index1, size_t index2)
{
    if (index1 == index2) return;

    pArr[index1] = pArr[index1] ^ pArr[index2];
    pArr[index2] = pArr[index1] ^ pArr[index2];
    pArr[index1] = pArr[index1] ^ pArr[index2];
}

// 大根堆 插入(元素上浮)
static void heapInsert(int* pArr, size_t index)
{
    while (pArr[index] > pArr[index / 2])
    {
        swap(pArr, index, index / 2);
        index = index / 2;
    }
}

#define MAX(a, b) (a > b ? a : b)

// 大根堆 堆化(元素下沉)
static void heapify(int* pArr, size_t heapSize, size_t index)
{
    while (index < heapSize)
    {
        size_t left = 2 * index + 1;
        size_t right = 2 * index + 2;
        int cur = pArr[index];
        if (left < heapSize && right < heapSize && cur < MAX(pArr[left], pArr[right]))
        {
            if (pArr[left] >= pArr[right])
            {
                swap(pArr, index, left);
                index = left;
            }
            else
            {
                swap(pArr, index, right);
                index = right;
            }
        }
        else if (left < heapSize && cur < pArr[left])
        {
            swap(pArr, index, left);
            index = left;
        }
        else break;
    }
}

//       i
//      /  \
//   i*2+1 i*2+2

//        (i-1)/2
//         /   \
//        i  or i

// 大根堆，任意一颗子树的跟节点的数字，大于等于子节点的数字
int main_HeapSort()
{
    int arr[] = { 3, 7, 8, 46, 0, 2, 50, 3, 4, 12, 99, 10, 9 };
    int size = sizeof(arr) / sizeof(int);
    int heapSize = 0;
    for (int i = 0; i < size; i++)
    {
        heapInsert(arr, i);
        ++heapSize;
    }

    for (int i = 0; i < size; i++)
    {
        swap(arr, 0, heapSize - 1);
        heapify(arr, --heapSize, 0);
    }

    return 0;
}